|
In computer science, recursive ascent parsing is a technique for implementing an LALR parser which uses mutually-recursive functions rather than tables. Thus, the parser is ''directly encoded'' in the host language similar to recursive descent. Direct encoding usually yields a parser which is faster than its table-driven equivalent〔(【引用サイトリンク】author=Thomas J Penello )〕 for the same reason that compilation is faster than interpretation. It is also (nominally) possible to hand edit a recursive ascent parser, whereas a tabular implementation is nigh unreadable to the average human. Recursive ascent was first described by Thomas Penello in his article in 1986. He was not intending to create a hand-editable implementation of an LR parser, but rather a maintainable and efficient parser implemented in assembly language. The technique was later expounded upon by G.H. Roberts〔(【引用サイトリンク】year=1988 )〕 in 1988 as well as in an article by Leermakers, Augusteijn, Kruseman Aretz〔(【引用サイトリンク】author=Leermakers, Augusteijn, Kruseman Aretz )〕 in 1992 in the journal ''Theoretical Computer Science''. An extremely readable description of the technique was written by Morell and Middleton in 2003. A good exposition can also be found in a TOPLAS article by Sperber and Thiemann.〔(【引用サイトリンク】author=Sperber and Thiemann )〕 Recursive ascent has also been merged with recursive descent, yielding a technique known as recursive ascent/descent. This implementation technique is arguably easier to hand-edit due to the reduction in states and fact that some of these states are more intuitively top-down rather than bottom up. It can also yield some minimal performance improvements over conventional recursive ascent.〔(【引用サイトリンク】author=John Boyland and Daniel Spiewak )〕 == Summary == Intuitively, recursive ascent is a literal implementation of the LR parsing concept. Each function in the parser represents a single LR automaton state. Within each function, a multi-branch statement is used to select the appropriate action based on the current token popped off the input stack. Once the token has been identified, action is taken based on the state being encoded. There are two different fundamental actions which may be taken based on the token in question: * Shift - Encoded as a function call, effectively jumping to a new automaton state. * Reduce - Encoded differently according to the semantic action routine for the relevant production. The result of this routine is wrapped in an ADT which is returned to the caller. The reduce action must also record the number of tokens which were shifted ''prior'' to the reduce, passing this value back to the caller along with the reduce value. This shift counter determines at which point up the call stack the reduce should be handled. There is also a third LR automaton action which may be taken in a given state, but only after a reduce where the shift counter has decremented to zero (indicating that the current state should handle the result). This is the goto action, which is essentially a special case of shift designed to handle non-terminals in a production. This action must be handled ''after'' the multi-branch statement, since this is where any reduction results will "resurface" from farther down the call stack. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Recursive ascent parser」の詳細全文を読む スポンサード リンク
|